//把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增排序的数组的一个旋转，
// 输出旋转数组的最小元素。例如，数组 [3,4,5,1,2 ] 为 [1,2,3,4,5] 的一个旋转，该数组的最小值为1。
//
// 示例 1： 
//
// 输入：[3,4,5,1,2]
//输出：1
// 
//
// 示例 2： 
//
// 输入：[2,2,2,0,1]
//输出：0
// 
//
// 注意：本题与主站 154 题相同：https://leetcode-cn.com/problems/find-minimum-in-rotated-sor
//ted-array-ii/ 
// Related Topics 二分查找 
// 👍 139 👎 0


package com.yun.leetcode.editor.cn;

public class XuanZhuanShuZuDeZuiXiaoShuZiLcof {
    public static void main(String[] args) {
        Solution solution = new XuanZhuanShuZuDeZuiXiaoShuZiLcof().new Solution();
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int minArray(int[] numbers) {
            // 想法，要先找到旋转点吗？
            // 答;貌似不用

            if (numbers.length == 0) {
                return 0;
            }
            int left = 0;
            int right = numbers.length - 1;

            while (left < right) {
                int mid = (left + right) / 2;
                if (numbers[mid] > numbers[right]) {
                    // 中间数大于右边数，是不是代表最小数在这之间
                    // .使用low=mid+1，而不是low=mid，最终会使得low=high（即最小值位置）而跳出循环；
                    left = mid + 1;
                } else if (numbers[mid] == numbers[right]) {
                    // 中间数等于右边数，有边界缩小一个
                    right = right - 1;
                } else {
                    //使用high=mid，而不是high=mid-1，因为有可能mid就是最小值点，不能减1；
                    right = mid;
                }

            }
            return numbers[left];
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

    // 尝试重写
    public int minAry(int[] numbers) {
        if (numbers.length == 0) {
            return 0;
        }
        int left = 0;
        int right = numbers.length -1;
        /*while (left < right) {
            int mid = (left + right)/2;
            if (numbers[mid] > numbers[right]) {
                left = mid +1;

            }else if(numbers[mid] == numbers[right]){
                right = right -1;
            }else{
                right = mid;
            }
        }

        return numbers[left];*/

        // 试试用右边写
        while (left < right) {
            int mid = (left+right)/2;
            if (numbers[mid] > numbers[left]) {
                right = mid;
            } else if (numbers[mid] < numbers[left]) {
                left = mid+1;
            }else {
                left = left+1;
            }
        }
        return 0;
    }
}